/*
160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路: 两个链表各自走到末尾，记录长度差(第一遍历n++,第二个遍历n--）
末尾节点相同则相交，否则不相交，根据长度差，一个头先走差值步，然后两个头同时走
相遇为结果
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) {
    return null
  }
  let p1 = headA
  let p2 = headB
  let delta = 0
  while (p1.next !== null) {
    delta++
    p1 = p1.next
  }
  while (p2.next !== null) {
    delta--
    p2 = p2.next
  }
  if (p1 !== p2) {
    // 不相交
    return null
  }
  p1 = delta > 0 ? headA : headB // p1 此时表示要先走delta步的链表, delta>0说明head1比head2长
  p2 = p1 === headA ? headB : headA
  delta = Math.abs(delta)
  while (delta) {
    p1 = p1.next
    delta--
  }
  while (p1 !== p2) {
    p1 = p1.next
    p2 = p2.next
  }
  return p1
}
